package com.guodaxia.gzh.web;

import java.util.HashMap;
import java.util.Map;

class RangeFreqQuery {
    //预先存起来结果
    Map<String, Map<Integer, Integer>> res = new HashMap<>();

    //预热数据
    //有重复的计算了
    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j >= 0; j--) {
                Map<Integer, Integer> lastMap = res.getOrDefault((j + 1) + "-" + i, new HashMap<>());
                Map<Integer, Integer> two = new HashMap<>(lastMap);
                two.put(arr[j], two.getOrDefault(arr[j], 0) + 1);
                res.put(j + "-" + i, two);
            }
        }
    }
    public int query(int left, int right, int value) {
        Map<Integer, Integer> orDefault = res.getOrDefault(left + "-" + right, new HashMap<>());
        int orDefault1 = orDefault.getOrDefault(value, 0);
        return orDefault1;
    }

    public static void main(String[] args) {
        int[] src = {937, 900, 967, 960, 989, 952, 962, 969, 964, 912, 965, 974, 966, 978, 904, 968, 951, 904, 930, 959, 988, 924, 959, 962, 994, 969, 960, 957, 986, 936, 933, 995, 990, 914, 978, 936, 994, 970, 994, 925, 986, 986, 986, 995, 949, 923, 941, 935, 957, 949, 999, 960, 921, 946, 963, 914, 959, 975, 999, 963, 930, 991, 942, 980, 995, 901, 914, 975, 963, 902, 984, 963, 904, 908, 913, 941, 964, 987, 956, 954, 958, 948, 960, 995, 947, 956, 960, 984, 997, 953, 952, 912, 992, 949, 976, 902, 984, 954, 963, 946, 939, 975, 945, 931, 950, 936, 917, 995, 979, 952, 942, 971, 939, 938, 914, 999, 965, 998, 972, 918, 967, 966, 940, 940, 982, 909, 930, 952, 962, 905, 902, 976, 985, 953, 901, 969, 943, 983, 936, 984, 947, 961, 976, 977, 973, 915, 963, 902, 931, 962, 961, 974, 969, 1000, 949, 963, 949, 970, 941, 993, 928, 978, 988, 926, 941, 957, 963, 977, 915, 927, 924, 979, 928, 909, 942, 951, 913, 948, 909, 968, 944, 947, 932, 978, 927, 945, 930, 1000, 934, 933, 915, 910, 914, 932, 979, 941, 924, 943, 954, 940, 980, 911, 918, 969, 969, 968, 967, 996, 971, 932, 930, 961, 950, 978, 909, 990, 905, 908, 991, 954, 965, 998, 918, 944, 943, 955, 936, 942, 903, 999, 995, 948, 969, 939, 943, 911, 978, 945, 931, 996, 923, 970, 976, 907, 943, 971, 928, 916, 969, 965, 992, 920, 943, 941, 961, 957, 912, 909, 966, 951, 973, 912, 977, 952, 937, 914, 907, 904, 999, 917, 964, 922, 915, 949, 997, 955, 905, 996, 901, 995, 984, 1000, 990, 915, 920, 921, 995, 992, 971, 964, 958, 992, 991, 972, 932, 908, 992, 934, 927, 946, 970, 925, 900, 912, 914, 912, 996, 942, 936, 988, 969, 921, 992, 991, 918, 999, 936, 986, 916, 996, 940, 937, 928, 972, 990, 986, 901, 963, 956, 988, 903, 948, 906, 924, 964, 1000, 968, 950, 980, 922, 907, 919, 927, 953, 974, 973, 986, 935, 973, 917, 990, 916, 957, 933, 906, 925, 942, 932, 936, 943, 969, 921, 937, 916, 906, 996, 929, 900, 911, 919, 971, 947, 956, 917, 964, 964, 982, 902, 928, 947, 946, 991, 902, 942, 911, 965, 945, 970, 968, 972, 948, 979, 958, 984, 982, 945, 977, 955, 987, 997, 961, 961, 900, 989, 904, 997, 934, 999, 937, 921, 999, 943, 908, 930, 986, 994, 909, 907, 948, 987, 933, 982, 960, 957, 982, 986, 923, 963, 924, 934, 953, 953, 944, 902, 964, 901, 919, 917, 980, 972, 908, 930, 930, 958, 924, 998, 978, 908, 997, 905, 933, 930, 953, 937, 970, 901, 953, 956, 964, 916, 993, 901, 980, 930, 995, 939, 977, 911, 909, 983, 948, 973, 913, 966, 994, 939, 989, 956, 916, 935, 947, 904, 953, 989, 926, 906, 990, 970, 983, 964, 947, 944, 982, 986, 943, 920, 974, 966, 914, 926, 970, 901, 977, 972, 948, 913, 982, 930, 998, 997, 924, 957, 943, 910, 916, 916, 903, 915, 948, 938, 987, 932, 987, 930, 906, 958, 948, 965, 999, 929, 901, 911, 963, 943, 972, 972, 946, 923, 926, 908, 932, 933, 965, 933, 959, 939, 921, 915, 921, 909, 966, 944, 999, 901, 981, 972, 965, 997, 990, 940, 964, 965, 901, 920, 901, 960, 974, 908, 929, 907, 969, 960, 988, 901, 910, 946, 907, 934, 957, 916, 957, 971, 961, 990, 939, 955, 976, 993, 985, 979, 992, 918, 983, 969, 995, 913, 931, 961, 975, 911, 904, 927, 942, 951, 965, 996, 909, 973, 938, 939, 954, 982, 907, 915, 996, 927, 973, 906, 999, 999, 904, 957, 931, 935, 934, 908, 924, 914, 966, 927, 972, 920, 986, 988, 918, 906, 999, 940, 984, 993, 993, 953, 991, 969, 970, 971, 923, 974, 956, 997, 939, 922, 980, 969, 942, 931, 946, 926, 949, 985, 947, 951, 939, 904, 947, 997, 914, 927, 915, 944, 916, 926, 947, 924, 986, 962, 969, 968, 926, 916, 972, 984, 985, 907, 925, 951, 984, 937, 996, 973, 923, 981, 988, 957, 903, 957, 972, 943, 915, 961, 932, 961, 953, 947, 987, 936, 992, 969, 991, 936, 908, 987, 988, 977, 965, 979, 938, 939, 916, 973, 978, 956, 929, 924, 997, 964, 906, 953, 978, 985, 900, 929, 979, 946, 977, 920, 910, 967, 906, 961, 905, 903, 998, 939, 912, 968, 901, 914, 986, 993, 913, 948, 939, 944, 919, 948, 991, 989, 935, 964, 967, 951, 961, 984, 999, 952, 919, 901, 951, 997, 936, 976, 973, 900, 947, 997, 980, 986, 900, 937, 965, 946, 959, 932, 982, 937, 949, 956, 909, 961, 950, 916, 923, 983, 989, 918, 967, 939, 993, 926, 974, 950, 910, 991, 920, 960, 936, 983, 950, 970, 928, 974, 915, 912, 904, 904, 929, 929, 952, 981, 936, 931, 910, 960, 917, 900, 953, 951, 939, 944, 912, 916, 916, 930, 939, 981, 998, 981, 928, 992, 911, 974, 983, 971, 990, 920, 997, 930, 942, 985, 955, 963, 992, 948, 955, 940, 917, 983, 934, 940, 945, 1000, 925, 941, 1000, 936, 905, 930, 901, 909, 946, 988, 931, 969, 949, 907, 952, 968, 975, 958, 972, 936, 902, 934, 955, 945, 999, 995, 917, 960, 934, 928, 933, 984, 959, 912, 937, 915, 963, 912, 951, 948, 977, 999, 956, 986, 983, 912, 973, 990, 925, 939, 967, 995, 973, 907, 1000, 928, 964, 918, 999, 925, 973, 938, 973, 960, 915, 954, 998, 990, 990, 962, 925, 938, 996, 966, 937, 918, 974, 997, 963, 927, 1000, 954, 985, 988, 905, 992, 959, 970, 924, 915, 995, 975, 928, 935, 932, 997, 974, 976, 977, 994, 981, 957, 905, 931, 998, 972, 977, 984, 996, 901, 904, 918, 982, 957, 913, 969, 937, 953, 974, 988, 923, 985, 904, 962, 912, 926, 988, 939, 922, 985, 962, 961, 919, 941, 902, 945, 976, 975};
        RangeFreqQuery rangeFreqQuery = new RangeFreqQuery(src);

        System.out.println(rangeFreqQuery.query(1, 1, 900));

    }

}
